package arithmetic.demo10;

import java.util.*;

/**
 * 题目： 哈希表_计算俩数之和
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
           int n = nums.length;
           int[] ret = new int[2];
           Map<Integer, Integer> hash = new HashMap<>();

            // 统计每个元素对应的下标
            for(int i = 0 ; i < n; i++) {
                int num = nums[i];
                if(hash.containsKey(num)) {
                    // 如果有重复就判断两个重复元素是否结果
                    if(2*num == target) {
                        ret[0] = i;
                        ret[1] = hash.get(num);
                        return ret;
                    }
                } else {
                    // 不存在就加入哈希表
                    hash.put(num, i);
                }
            }


            for(int i = 0; i<n; i++) {
                int num = nums[i];
                // 查找是否有剩余元素子啊哈希表中
                // 一旦有就存储下标，返回结果
                if(hash.containsKey(target-num) && hash.get(target-num) != i) {
                    ret[0] = i;
                    ret[1] = hash.get(target-num);
                    return ret;
                }
            }


            
            return ret;
    }
}


/**
 * 方法二： 从后往前搜索
 */
class Solution1 {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[] ret = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();

        // 边加入哈希表
        // 边查找前面是否有值相等
        for(int i =0; i < n; i++) {
            int num = nums[i];
            if(hash.containsKey(target - num)) {
                ret[0] = hash.get(target-num);
                ret[1] = i;
            } else {
                hash.put(num, i);
            }
        }


        return ret;
    }
}


/**
 * 题目： 哈希表_判断字符串是否重排
 */

class Solution2 {
    public boolean CheckPermutation(String s1, String s2) {
        // 长度不同的特殊情况处理
        if(s1.length() != s2.length()) {
            return false;
        }

        int[] hash1 = new int[26];
        int[] hash2 = new int[26];

        // 先一起统计 s1 和 s2 出现的字符种类个数
        for(int i =0; i<s1.length() ; i++) {
            hash1[s1.charAt(i) - 'a'] ++;
            hash2[s2.charAt(i) - 'a'] ++;
        }

        //  然后一个字符一个字符判断是否是种类和个数相同
        for(int i =0; i< 26; i++) {
            // 一旦有不相同的就返回 false
            if(hash1[i] != hash2[i]) {
                return false;
            }
        }


        return true;

    }
}


/**
 * 题目： 哈希表_存在重复元素
 */

class Solution3{
    public boolean containsDuplicate(int[] nums) {
        // 使用set 来判断是否重复
        Set<Integer> set = new HashSet<>();
        int n=nums.length;
        for(int i=0;i < n;i++) {
            int num=nums[i];
            // 一旦有重复就返回 true
            if(set.contains(num)) {
                return true;
            } else {
                set.add(num);
            }
        }


        return false;
    }
}


/**
 * 题目： 哈希表_存在重复元素(2)
 */

class Solution4 {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> hash = new HashMap<>();

        for(int i =0; i< n;i++) {
            int num = nums[i];
            // 一旦包含重复元素
            // 并且重复的位置<= k
            if(hash.containsKey(num) && (i - hash.get(num)) <= k) {
                return true;
            } else {
                // 即使重复 不满足 <= k 就更新结果
                hash.put(num, i);
            }
        }


        return false;
    }
}


/**
 * 题目： 哈希表_字母异位词分组
 */


class Solution5 {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 初始化
        List<List<String>> ret = new ArrayList<>();
        Map<String, Integer>  hash = new HashMap<>();
        int n =  strs.length;
        int j =0;
        for(int i =0; i<n; i++) {
            String str1 = change(strs[i]);
            if(hash.containsKey(str1)) {
                // 给当前位置继续加入字符串
                ret.get(hash.get(str1)).add(strs[i]);
            } else {
                // 先new 上一个空间 并加入该位置
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                ret.add(list);

                // 加入到哈希表中
                hash.put(str1, j++);
            }

        }

        return ret;
    }


    private String change(String str) {

        // 初始化
        int n= str.length();
        int[] hash = new int[26];

        // 存储结果
        StringBuilder  ret = new StringBuilder();

        // 开始统计
        for(int i =0; i<n;i++) {
            char ch = str.charAt(i);
            hash[ch-'a']++;
        }

        // 计数排序返回
        for(int i = 0; i<26; i++) {
            int k = hash[i];
            while(k-- >0) {
                ret.append((char)(i+'a'));
            }
        }

        return ret.toString();


    }
}

/**
 * 题目： 代码二， 字母异位分组
 */


class Solution6 {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个 k 为 String ， v 为 List<String> 的哈希表
        Map<String , List<String>>  hash = new HashMap<>();

        for(int i  = 0; i < strs.length; i++) {
            // 转化成数组进行排序
            char[] chs =strs[i].toCharArray();
            Arrays.sort(chs);

            // 重新转化为字符串
            String str = new String(chs);
            // 一旦存在就 new 出新空间
            if(!hash.containsKey(chs)) {
                hash.put(str, new ArrayList<>());
            }

            // 进入哈希
            hash.get(str).add(strs[i]);
        }


        return new  ArrayList<>(hash.values());
    }
}


/**
 * 题目： 字符串_最长公共前缀
 * 方案一： 全体同位比较
 */

class Solution7 {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0 ) return "";
        if(strs.length == 1) return strs[0];

        int pos = 0;
        while(true) {

            boolean flg = false;
            //  一旦有不相等的就跳出
            for(int i = 0;i < strs.length - 1; i++) {
                if(pos >= strs[i].length() || pos >= strs[i+1].length()
                        || strs[i].charAt(pos) != strs[i+1].charAt(pos)) flg = true;
            }

            // 如果直接break 跳出 或者pos 已经到达边界
            if(flg) break;

            pos++;

        }


        return  pos == 0 ? "":  strs[0].substring(0, pos);

    }
}


